package bishi.dada.huanju;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/11/30 21:04
 */
public class two {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i] * this.lr(nums, i - 1, i + 1);
        }
        for (int l = n - 1; l >= 0; l--) {
            for (int r = l + 1; r < n; r++) {
                int lr = this.lr(nums, l - 1, r + 1);
                int max = dp[l + 1][r] + nums[l] * lr;
                max = Math.max(max, dp[l][r - 1] + nums[r] * lr);
                for (int i = l + 1; i < r; i++) {
                    max = Math.max(max, dp[l][i - 1] + dp[i + 1][r] + nums[i] * lr);
                }
                dp[l][r] = max;
            }
        }
        return dp[0][n - 1];
    }

    private int lr(int[] nums, int l, int r) {
        int lnum = l == -1 ? 1 : nums[l];
        int rnum = r == nums.length ? 1 : nums[r];
        return lnum * rnum;
    }
}
